package leetcode_500;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 *@author 周杨
 *BinaryWatch_401 二进制手表 给定一个正整数  表示有几个灯亮 返回当前可能的时间
 *describe:用深度搜索 AC 99%
 *2018年7月17日 上午11:06:55
 */
public class BinaryWatch_401 {
	List<String> res;
	public static void main(String[] args) {
		BinaryWatch_401 test=new BinaryWatch_401();
		test.readBinaryWatch(7);
	}
	/**
	 * describe:不知哪里出了问题
	 * 2018年7月17日 上午11:20:22
	 */
	public List<String> readBinaryWatch(int num) {
        this.res=new ArrayList<String>();
        List<List<String>> hour=new ArrayList<List<String>>();
        List<String> hour0=new ArrayList<String>();
        hour0.add("0");
        List<String> hour1=new ArrayList<String>();
        hour1.add("1");
        hour1.add("2");
        hour1.add("4");
        hour1.add("8");
        List<String> hour2=new ArrayList<String>();
        hour2.add("3");
        hour2.add("5");
        hour2.add("9");
        hour2.add("6");
        hour2.add("10");
        List<String> hour3=new ArrayList<String>();
        hour3.add("7");
        hour3.add("11");
        
        hour.add(hour0);
        hour.add(hour1);
        hour.add(hour2);
        hour.add(hour3);
        
        Map<Integer,List<String>> map=new HashMap<Integer,List<String>>();
        for(int i=0;i<60;++i) {
        	int count=Integer.bitCount(i);
        	List<String> list=map.get(count);
        	String value=String.valueOf(i);
    		if(value.length()==1)
    			value=":0"+value;
    		else
    			value=":"+value;
        	if(list==null) {
        		list=new ArrayList<String>();
        		list.add(value);
        		map.put(count, list);
        	}
        	else {
        		list.add(value);
        	}
        }
        /*for(int i=0;i<=num&&i<=5;++i) {//分钟最大是5
        	List<String> m=map.get(i);
        	if(num-i>=3)
        		continue;
        	List<String> h=hour.get(num-i);
        	for(int j=0;j<m.size();++j)
        		for(int k=0;k<h.size();++k) {
        			this.res.add(h.get(k)+m.get(j));
        		}
        }*/
        
        for(int i=0;i<=num&&i<=3;++i) {
        	List<String> h=hour.get(i);
        	if(num-i>=5)
        		continue;
        	List<String> m=map.get(num-i);
        	for(int j=0;j<h.size();++j)
        		for(int k=0;k<m.size();++k) {
        			this.res.add(h.get(j)+m.get(k));
        		}
        }
        
        return this.res;
    }
	
	 int[] hours = new int[]{1,2,4,8};
	    int[] mins = new int[]{1,2,4,8,16,32};
	    // List<String> res= new ArrayList<>(); 
	    
	    public List<String> readBinaryWatch1(int num) {
	        List<String> res = new ArrayList<>();
	        if(num> 10 || num<0) return res;
	        
	        for(int i=0;i<=num && i<hours.length;i++){
	            List<Integer> hour = getNum(i,hours,new ArrayList<Integer>(),0,0);
	            List<Integer> min = getNum(num-i,mins,new ArrayList<Integer>(),0,0) ;

	            for(int x: hour){
	                if(x>=12) continue;
	                 for( int y : min){
	                    if(y>=60) continue;
	                    StringBuilder sb = new StringBuilder();
	                    sb.append(x);
	                    sb.append(":");
	                    sb.append(y<10?"0"+y:y);
	                    res.add(sb.toString());
	                }
	            }  
	        }
	        return res;     
	    }
	    private List<Integer> getNum(int nums, int[] arr, List<Integer> curr, int sum,int idx){
	     
	        if(nums==0){
	            curr.add(sum);
	            return curr;
	        }
	        for(int i=idx;i<arr.length;i++){
	           getNum(nums-1,arr,curr,sum+arr[i],i+1); 
	        }
	        return curr;
	    }
	
	
	
}
